IA. Field of the Invention
The invention relates to scan techniques for sequential circuits. In particular, this invention relates to new partial scan techniques using peripheral partitioning and tree decomposition. The invention is embodied in a system to perform partial scan using peripheral partitioning and tree decomposition, in a method for partial scan using peripheral partitioning, in a method for partial scan using tree decomposition, and in a computer program product for enabling a computer to operate according to the method.
IB. Related Work
Complexity of testing sequential circuits is well known in the prior art. Two fundamentally different approaches have been pursued in the prior art to reduce the complexity of testing sequential circuits: (1) a synthesis approach, where practitioners synthesize circuits that are easy to test, and/or (2) a design for testability approach, where post-synthesis modification techniques are employed to facilitate easy testing of the circuit.
The synthesis approach requires prohibitive computational resources. Also, when a hierarchical design methodology is used, integrating testability requirements involving different blocks or modules is difficult.
Design for testability techniques such as scan have been used widely for achieving high test coverage for sequential circuits. In scan techniques, memory elements (including flip-flops) in a circuit are chained into a shift register. A full scan involves the chaining of all the shift registers in the circuit to be tested. Scan provides for direct controllability and observability of all memory elements during the test mode. However, area and performance penalties of full scan design are unacceptable for many sequential circuit designs.
Partial scan techniques involve selecting only a subset of memory elements. This reduces area and performance penalties involved in a full scan.
Several approaches for selecting memory elements for partial scan have been suggested in the prior art. Testability analysis based approach is one of the approaches that is known in the prior art. See E. Trischler, "Incomplete Scan Path with an Automatic Test Generation Methodology," in Proceedings of the international Test Conference, pp. 153-162, 1980; M. Abramovici, J. J. Kulikowski, and R. K. Roy, "The Best Flip-Flops to Scan," in Proceedings of the International Test Conference, pp. 166-173, 1991; K. S. Kim and C. R. Kime, "Partial Scan by Use of Empirical Testability," in Proceedings of the International Conference on Computer-Aided Design, pp. 314-317, November 1990; P. S. Parikh and M. Abramovici, "A Cost Based Approach to Partial Scan," in Proceedings of the 30th ACM/IEEE Design Automation Conference, pp. 255-259, June 1993 and D. Xiang and J. H. Patel, "A Global Algorithm for the Partial Scan Design Problem using Circuit State Information," in Proceedings of the International Test Conference, pp. 548-557, October 1996.
Another method suggested in the prior art is a test generation based approach. See V. D. Agrawal, K. T. Cheng, D. D. Johnson, and T. Lin, "Designing Circuits with Partial Scan," IEEE Design and Test of Computers, vol. 5, pp. 8-15, April 1988; H.-K. T. Ma, S. Devadas, A. R. Newton, and A. Sangiovanni-Vincentelli, "An Incomplete Scan Design Approach to Test Generation for Sequential Machines," in Proceedings of the International Test Conference, pp. 730-734, 1988; V. Chickermane and J. H. Patel, "A Fault Oriented Partial Scan Design Approach," in Proceedings of the International Conference on Computer-Aided Design, pp. 400-403, November 1991; I. Park, D. S. Ha, and G. Sim, "A New Method for Partial Scan Design based on Propagation and Justification Requirements of Faults," in Proceedings of the International Test Conference, pp. 413-422, October 1995; and V. Boppana and W. K. Fuchs, "Partial Scan Design based on State Transition Modeling," in Proceedings of the International Test Conference, pp. 538-547, October 1996.
Functional or state machine analysis based approaches have also been used in the prior art. See V. Boppana and W. K. Fuchs, "Partial Scan Design based on State Transition Modeling," in Proceedings of the International Test Conference, pp. 538-547, October 1996; C.-C. Lin, M. T.-C. Lee, M. Marek-Sadowska, and K.-C. Chen, "Cost Free Scan: A Low Overhead Scan Path Design Methodology," in Proc. of the International Conference on Computer-Aided Design, November 1995; C. C. Lin, M. Marek-Sadowska, K. T. Cheng, and M. T. C. Lee, "Test Point Insertion: Scan Paths through Combinational Logic," in Proceedings of the 32nd ACM/IEEE Design Automation Conference, pp. 268-273, June 1995; D. Chang, M. T. C. Lee, M. Marek-Sadowska, T. Aikyo, and K. T. Cheng, "A Test Synthesis Approach to Reducing BALLAST DFT Overhead," in Proceedings of the 34th ACM/IEEE Design Automation Conference, pp. 466-471, June 1997.
Several practitioners have used a structural analysis based approach. See R. Gupta, R. Gupta, and M. A. Breuer, "The BALLAST Methodology for Structured Partial Scan Design," IEEE Transactions on Computers, vol. C-39, pp. 538-544, April 1990; K. T. Cheng and V. D. Agrawal, "A Partial Scan Method for Sequential Circuits with Feedback," IEEE Transactions on Computers, vol. 39, pp. 544-548, April 1990; D. Lee and S. Reddy, "On Determining Scan Flip-Flops in Partial-Scan Designs," in Proceedings of the International Conference on Computer-Aided Design, pp. 322-325, November 1990; A. Kunzmann and H. J. Wunderlich, "An Analytical Approach to the Partial Scan Problem," Journal of Electronic Testing: Theory and Applications, vol. 1, pp. 163-174, 1990; S. Bhawmik, C. J. Lin, K. T. Cheng, and V. D. Agrawal, "Pascant: A Partial Scan and Test Generation System," in Custom Integrated Circuits Conference, pp. 17.3.1-17.3.4, 1991; S. E. Tai and D. Bhattacharya, "A Three Stage Partial Scan Design Method using the Sequential Circuit Flow Graph," in Proceedings of the 7th International Conference on VLSI Design, pp. 101-106, January 1994; S. T. Chakradhar, A. Balakrishnan, and V. D. Agrawal, "An Exact Algorithm for Selecting Partial Scan Flip-Flops," in Proc. of the 31st ACM/IEEE Design Automation Conf., pp. 81-86, June 1994; A. Balakrishnan and S. T. Chakradhar, "Sequential Circuits with Combinational Test Generation Complexity," in 9th International Conference on VLSI Design, January 1996; and T. Ono, "Selecting Partial Scan Flip-flops for Circuit Partitioning," in Proceedings of the International Conference on Computer-Aided Design, pp. 646-650, November 1994.
The testability analysis based methods use cost metrics during scan selection. The ability of testability based approaches to tightly correlate with sequential test generation effort required for large designs is not clearly established. Further, one often has to rely on the test generator to refine the measures and/or to gain confidence on the scan selection based on these testability measures. Some of the more sophisticated testability measures require large computational resources.
Test generation based approaches select scan memory elements based on identification of hard-to-detect faults. This approach is tightly coupled with the test generation tool and does not offer the designer any flexibility to determine scan flip-flops a priori. Further, scan selection strongly depends on the order of faults chosen by the test generation.
Often, one may have to perform multiple test generation runs to obtain good scan selection. This approach further constraints the already computationally intensive test generation process. Recent work by V. Boppana and W. K. Fuchs incorporates state machine analysis within the test generation based approach to select partial scan flip-flops. The applicability of such approaches to large designs have not been established.
Another recent functional approach showed that functional or cost-free scan paths can be established for any scan selection. See C.-C. Lin et al., "Cost Free Scan: A Low Overhead Scan Path Design Methodology," in Proc. of the International Conference on Computer-Aided Design, November 1995. This method involves computation of ordered binary decision diagrams (OBDD's). Therefore, it may prove to be computationally expensive for large designs.
Other recent efforts have shown the use of test points to establish functional scan paths. See C. C. Lin, M. Marek-Sadowska, K. T. Cheng, and M. T. C. Lee, "Test Point Insertion: Scan Paths through Combinational Logic," in Proceedings of the 32nd ACM/IEEE Design Automation Conference, pp. 268-273, June 1995 and D. Chang, M. T. C. Lee, M. Marek-Sadowska, T. Aikyo, and K. T. Cheng, "A Test Synthesis Approach to Reducing BALLAST DFT Overhead," in Proceedings of the 34th ACM/IEEE Design Automation Conference, pp. 466-471, June 1997. These techniques can be used to complement any scan selection approach, including the present invention, to provide an effective way to implement/synthesize scan chains.
Structural partial scan methods analyze the structure of the flip-flop dependency graph and base their scan selection on structural properties of this graph. Most of the structural methods have centered around breaking feedback loops, a technique first introduced by Cheng et al. See Cheng and V. D. Agrawal, "A Partial Scan Method for Sequential Circuits with Feedback," IEEE Transactions on Computers, vol. 39, pp. 544-548, April 1990. This approach called self-loop acyclic all feedback loops except self-loops are broken. A self-loop here refers to a situation where the output of a flip-flop, after passing through combinational logic, feeds back into the same flip-flop. This approach results in low area overhead, however, it is not effective for test generation.
At the other extreme one can break all feedback loops including self-loops. This approach called pipeline, results in a scan circuit with almost combinational ATPG complexity. See H. B. Min and W. A. Rogers, "A Test Methodology for Finite State Machines using Partial Scan Design," Journal of Electronic Testing: Theory and Applications, vol. 3, pp. 127-137, May 1992. However, this approach can result in high area overhead because most of the flip-flops in a typical design have self-loops. An extension of the pipeline approach advocates limiting the sequential depth of the design during the test mode.
Several partial scan techniques have been proposed recently but they either lack the ability to provide adequate test coverage for modest to large designs or they do not yield significant reduction in area/performance penalties as compared to full scan design. For example, consider the two analogous approaches for partial scan: one selecting flip-flops to break all feedback cycles except self-loops (self-loop acyclic) and the other selecting flip-flops to break all feedback cycles including self-loops (pipeline). FIG. 13 depicts a table showing area overhead and test generation results for the larger benchmark circuits. The data shows that self-loop acyclic technique entails low area overhead but the scanned circuits are hard to test. Pipeline method produces circuits that are easy to test but this method entails high area overhead.